/**
 * 碰撞检测四叉树类
 * 2018/11/12 
 */
class Quadtree {
    private MAX_OBJECTS :number = 10;//四叉树的子节点的最大个数
    private MAX_LEVELS :number = 5;//四叉树的最大深度

    private level :number;        // 子节点深度
    private objects :Array<any>;     // 物体数组
    private bounds :egret.Rectangle; // 区域边界
    private nodes // 四个子节点
    
    public constructor(pBounds :egret.Rectangle, pLevel?: number)
    {
        this.level = pLevel === void 0 ? 0 : pLevel;
        this.bounds = pBounds;
        this.objects = new Array<any>();
        this.nodes = [];
    }

    /*
    * 清空四叉树
    */
    public clear() {
        for(let v of this.objects)
        {
            v.destory();
        }
        this.objects = [];

        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i] != null) {
                this.nodes[i].clear();
                this.nodes[i] = null;
            }
        }
    }

    /*
    * 将一个节点分成四个子节点（实际是添加四个子节点）
    */
    private split() {
        let subWidth = (this.bounds.width / 2);
        let subHeight = (this.bounds.height / 2);
        let x = this.bounds.x;
        let y = this.bounds.y;

        this.nodes[0] = new Quadtree(new egret.Rectangle(x + subWidth, y, subWidth, subHeight), this.level + 1);
        this.nodes[1] = new Quadtree(new egret.Rectangle(x, y, subWidth, subHeight), this.level + 1);
        this.nodes[2] = new Quadtree(new egret.Rectangle(x, y + subHeight, subWidth, subHeight), this.level + 1);
        this.nodes[3] = new Quadtree(new egret.Rectangle(x + subWidth, y + subHeight, subWidth, subHeight), this.level + 1);   
    }

    /*
    * 用于判断物体属于哪个子节点
    * -1指的是当前节点可能在子节点之间的边界上不属于四个子节点而还是属于父节点
    */

    private getIndex(pRect:any) {
        let index = -1;
        // 中线
        let verticalMidpoint = this.bounds.x + (this.bounds.width / 2);
        let horizontalMidpoint = this.bounds.y + (this.bounds.height/ 2);

        // 物体完全位于上面两个节点所在区域
        let topQuadrant = (pRect.y < horizontalMidpoint && pRect.y + pRect.height <= horizontalMidpoint);
        // 物体完全位于下面两个节点所在区域
        let bottomQuadrant = (pRect.y >= horizontalMidpoint);

        // 物体完全位于左面两个节点所在区域
        if (pRect.x < verticalMidpoint && pRect.x + pRect.width <= verticalMidpoint) {
            if (topQuadrant) {
                index = 1; // 处于左上节点 
            }
            else if (bottomQuadrant) {
                index = 2; // 处于左下节点
            }
            }
        // 物体完全位于右面两个节点所在区域
        else if (pRect.x >= verticalMidpoint) {
            if (topQuadrant) {
            index = 0; // 处于右上节点
            }
            else if (bottomQuadrant) {
            index = 3; // 处于右下节点
            }
        }

        return index;
    }

    /*
    * 将物体插入四叉树
    * 如果当前节点的物体个数超出容量了就将该节点分裂成四个从而让多数节点分给子节点
    */
    public insert(pRect:any) {   
        let objs = this.objects, i, index;
    
        // 如果该节点下存在子节点
        if (this.nodes.length > 0) {
            index = this.getIndex(pRect);
            if (index !== -1) {
                if(this.nodes[index])
                this.nodes[index].insert(pRect);
                return;
            }
        }
    
        // 否则存储在当前节点下
        objs.push(pRect);
    
        // 如果当前节点存储的数量超过了MAX_OBJECTS
        if (this.nodes.length == 0 &&
            this.objects.length > this.MAX_OBJECTS &&
            this.level < this.MAX_LEVELS) {
    
            this.split();
    
            for (i = objs.length - 1; i >= 0; i--) {
                index = this.getIndex(objs[i]);
                if (index !== -1) {
                    if(this.nodes[index])
                    this.nodes[index].insert(objs.splice(i, 1)[0]);
                }
            }
        }
        
    }
    
    /*
    * 返回所有可能和指定物体碰撞的物体
    */
    public retrieve (rect:any) {
        let index;
        let result = [];
    
        if (this.nodes.length > 0) {
            index = this.getIndex(rect);
            if (index !== -1) {
                result = result.concat(this.nodes[index].retrieve(rect));
            } else{
                let arr = this.carve(rect);
                for (let i = arr.length - 1; i >= 0; i--) {
                    index = this.getIndex(arr[i]);
                    if(index != -1)
                    result = result.concat(this.nodes[index].retrieve(arr[i]));
                }
            }
        }

        result = result.concat(this.objects);
    
        return result;
    }

    /**
     * 按边界切割node重新生成节点
     */
    public carve(rect:any)
    {
        // 中线
        let verticalMidpoint = this.bounds.x + (this.bounds.width / 2);
        let horizontalMidpoint = this.bounds.y + (this.bounds.height/ 2);

        let arr = [];

        //左存在
        if(rect.x < verticalMidpoint)
        {
            if(rect.y < horizontalMidpoint)
            {
                let rect1 = new egret.Rectangle(rect.x, rect.y, verticalMidpoint - rect.x, horizontalMidpoint - rect.y);
                arr.push(rect1);
            }
            if(rect.y + rect.height > horizontalMidpoint)
            {
                let rect2 = new egret.Rectangle(rect.x, horizontalMidpoint, verticalMidpoint - rect.x, rect.y + rect.height - horizontalMidpoint);
                arr.push(rect2);
            }
        }
        if(rect.x + rect.width>= verticalMidpoint)
        {
            if(rect.y < horizontalMidpoint)
            {
                let rect3 = new egret.Rectangle(verticalMidpoint, rect.y, rect.x + rect.width - verticalMidpoint , horizontalMidpoint - rect.y);
                arr.push(rect3);
            }
            if(rect.y + rect.height > horizontalMidpoint)
            {
                let rect4 = new egret.Rectangle(verticalMidpoint, horizontalMidpoint, rect.x + rect.width - verticalMidpoint, rect.y + rect.height - horizontalMidpoint);
                arr.push(rect4);
            }
        }

        return arr;
    }
 
    /*
        动态更新：
        从根节点深入四叉树，检查四叉树各个节点存储的物体是否依旧属于该节点（象限）的范围之内，如果不属于，则重新插入该物体。
    */
    public refresh (root?){
        let isInner = function(rect, bounds)
        {
            return  rect.x >= bounds.x &&
                    rect.x +  rect.width <= bounds.x + bounds.width &&
                    rect.y >= bounds.y &&
                    rect.y + rect.height <= bounds.y + bounds.height;
        }

        let objs = this.objects, rect, index, i, len;
    
        root = root || this;
    
        for (i = objs.length - 1; i >= 0; i--) {
            rect = objs[i];
            index = this.getIndex(rect);
    
            // 如果矩形不属于该象限，则将该矩形重新插入
            if (!isInner(rect, this.bounds)) {
                if (this !== root) {
                    root.insert(objs.splice(i, 1)[0]);
                }
    
            // 如果矩形属于该象限 且 该象限具有子象限，则
            // 将该矩形安插到子象限中
            } else if (this.nodes.length) {
                if(this.nodes[index])
                this.nodes[index].insert(objs.splice(i, 1)[0]);
            }
        }
    
        // 递归刷新子象限
        for (i = 0, len = this.nodes.length; i < len; i++) {
            this.nodes[i].refresh(root);
        }
    }

    /**
     * 移除
     */
    public remove(list)
    {
        for(let i=this.objects.length -1;i >=0 ;i--)
        {
            let node = this.objects[i];
            if(list[node.name])
            {
                this.objects.splice(i, 1);
                node.dispos();
                list[node.name] = null;
                // if (Bullet._pools.indexOf(node) == -1)
			    //     Bullet._pools.push(node);
            }
        }

        for(let i=0;i < this.nodes.length;i++)
        {
            this.nodes[i].remove(list)
        }
    }

    /*
     * 得到四叉树中所有的需要检测的对象
     */
    public getAllObjects(returnedObjects)
    {
        for (var i = 0, len = this.objects.length; i < len; i++) {
            returnedObjects.push(this.objects[i]);
        }

        for (var i = 0; i < this.nodes.length; i++) {
            if(this.nodes[i])
            this.nodes[i].getAllObjects(returnedObjects);
        }
    }

    /**
     * 使每个对象都执行方法
     */
    public AllObjectsDone(type?)
    {
        let len = this.objects.length;
        for(let i=0;i < len;i++)
        {
        }

        for (var i = 0; i < this.nodes.length; i++) {
            this.nodes[i].AllObjectsDone(type);
        }

    }
}
